package main

import (
	"fmt"
)

func main() {
	s := "-  6   + 10 *   (2 - 3)   - 4"
	fmt.Println(calculate(s))
}

/**
知识点： 栈 指针 递归

收获：要学会拆解复杂问题

思路：
1. 先解决在字符串中获取数字，如 " ef 1234fga" 能拿到数字 1234
2. 接着先只考虑 加减 运算，如 -1 + 5 - 2 , 直接入栈 -1、+5、-2
3. 接着加入 乘除 运算，和 2 的步骤类似，2 是直接入栈，这里 要先把栈顶的值拿出来 prev 和 当前值 num 相 乘或除，把结果入栈
4. 接着加入 括号，这里在 3 的基础上进行 递归 操作，因为括号其实就是一个值，这个值可以在 3 的基础上递归得到，碰到 ( 进入递归，碰到 ) 跳出循环
5. 去除空格
6. 最后把栈的结果全部相加即为所求结果
7. 栈可以用单链表实现，因为只对头元素增加和删除
 */

func calculate(s string) int {
	tempS := s
	return toCalculate(&tempS)
}

func toCalculate(s *string) int {
	/**
	这里 num 为 sign 后面的整数，sign 为 num 前面的符号，
	如 5 - 3，即 +5、-3，sign 为 +，num 为 5，或者 sign 为 -，num 为 3
	是一对一对出现的
	 */
	num, sign, res := 0, byte('+'), 0
	stack := make([]int, 0, len(*s))

	for len(*s) > 0 {
		tempS := *s
		val := tempS[0]
		tempS = tempS[1:]
		// 去除第一个值
		*s = tempS

		if val == '(' {
			// 算出括号的值
			num = toCalculate(s)
		}

		if val >= '0' && val <= '9' {
			// 获取字符串里的整数
			num = num * 10 + int(val - '0')
		}

		// 不是数字 或者 是最后一个字符
		if val < '0' || val > '9' || len(tempS) == 0 {
			// 去除空格
			if val == ' ' && num == 0 {
				continue
			}

			switch sign {
			case '+':
				stack = append(stack, num)
			case '-':
				stack = append(stack, -num)
			case '*':
				prev := stack[len(stack) - 1]
				stack = stack[:len(stack) - 1]
				stack = append(stack, prev * num)
			case '/':
				prev := stack[len(stack) - 1]
				stack = stack[:len(stack) - 1]
				stack = append(stack, prev / num)
			}

			sign = val
			num = 0
		}

		// 跳出递归中的循环
		if val == ')' {
			break
		}
	}

	// 统计结果
	for i := len(stack) - 1; i >= 0 ; i-- {
		res += stack[i]
	}

	return res
}
